package baseclass.j_dp.recursion;

import java.util.Arrays;
import java.util.HashSet;
import java.util.TreeSet;

/**
 * @date 2020/3/1 15:35
 */
public class Test {
    //例1：n！，通过 本质 n! = n* n-1!
    public static long getFactorial(int n){
        if (n == 1)
            return 1;
        return n*getFactorial(n-1);
    }

    //例2：给定一个字符串，求该字符串的所有可能子串，包括空串
    /**
     * 分析：从左到右每个位置只有两种可能，要或不要，递归穷举。
     * index = 0开始时是基于在""空串的前提下拼接
     */
    public static void printAllSubString(char [] str,int index, String res){
        //超出最后一个位置
        if(index == str.length) {
            System.out.println(res);
            return;
        }
        //index位置不要，
        printAllSubString(str,index + 1, res+" ");
        //index位置要
        printAllSubString(str,index + 1, res+String.valueOf(str[index]));
    }

    /**
     * 例3:打印一个字符串的全排列：如abc
     *      思路 对于第一个位置有三种可能，abc。第一个位置和a换，和b换 ，和c换
     *          第二个位置，在第一个位置确定下有两种可能，和自己换，和后一个换。
     *          第三个位置，在前两个位置确定下有1中可能，就是和自己换。
     */
    public static void printAllPermutations(String str){
        char[] chars = str.toCharArray();
        process(chars,0);
    }

    private static void process(char[] chars, int index) {
        if(index == chars.length) System.out.println(Arrays.toString(chars));
        //从当前位置index开始和后面的一一交换
        for (int i = index; i < chars.length; i++) {
            swap(chars,index,i);
            process(chars,index+1);
            swap(chars,i,index);
        }
    }
    //全排列2：对重复的不进行再次排列。如aca,index = 0与i=0,1,2换，当char[index] = char[i]是重复状态，不交换。
    public static void printAllPermutations2(String str) {
        char[] chs = str.toCharArray();
        process2(chs, 0);
    }

    //利用TreeSet可以排除重复{a,a} 只要一个排列，并且可以按照字典顺序输出
    private static TreeSet<String> res = new TreeSet<>();

    private static void process2(char[] chs, int index) {
        if (index == chs.length) {
            res.add(new String(chs));
            System.out.println(String.valueOf(chs));
        }
        //每次进入递归都会针对当前位置i进行new 一个hashSet
        HashSet<Character> set = new HashSet<>();
        for (int i = index; i < chs.length; i++) {
            //不重复才发生交换,这里属于提前剪枝
            if (!set.contains(chs[i])) {
                set.add(chs[i]);
                swap(chs, index, i);
                process2(chs, index + 1);
                //记得交换回来
                swap(chs, index, i);
            }
        }
    }

    private static void swap(char[] chars, int i, int j) {
        if(i == j) return;
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    public static void main(String[] args) {
        printAllPermutations("abc");
        printAllPermutations2("aba");
        System.out.println("=====");
        res.forEach(System.out::println);
    }
}
